package org.example.BinaryTree;

import java.util.HashMap;

public class Construct_a_binary_tree {
    public static HashMap<Integer,Integer> hashMapIn = new HashMap<Integer,Integer>();
//    public static HashMap<Integer,Integer> hashMapPost = new HashMap<Integer,Integer>();
    public static void main(String[] args) {
        //从中序与后序遍历序列构造二叉树

        //给定两个整数数组 inorder 和 postorder ，其中 inorder 是二叉树的中序遍历， postorder 是同一棵树的后序遍历，请你构造并返回这颗 二叉树 。
        int[] inorder = {2,3,1};
        int[] postorder = {3,2,1};
        TreeNode root = buildTree(inorder, postorder);
        search(root);
    }
    public static TreeNode buildTree(int[] inorder, int[] postorder) {
        if (postorder.length==0) return null;
        for (int i = 0; i < inorder.length; i++) {
            hashMapIn.put(inorder[i],i);
        }
        return get(inorder,0,inorder.length-1,postorder,0, postorder.length-1);
    }
    public static TreeNode get(int[] inorder,int beforeIn,int afterIn,int[] postorder,int beforePost,int afterPost){
        if (beforeIn > afterIn || beforePost > afterPost) return null;
        TreeNode node = new TreeNode(postorder[afterPost]);
        //System.out.println(node.val);
        Integer indexIn = hashMapIn.get(postorder[afterPost]);
        Integer lenofleft = indexIn-beforeIn;
        node.left = get(inorder,beforeIn,indexIn-1,postorder,beforePost,beforePost+lenofleft-1);
        node.right = get(inorder,indexIn+1,inorder.length-1,postorder,beforePost+lenofleft,afterPost-1);
        return node;
    }

    //遍历
    public static void search(TreeNode root){
        if (root==null) return;
        search(root.left);
        search(root.right);
        System.out.println(root.val);
    }
}
